package 力扣.并查集;

public class 岛屿数量200 {
    //如何在二维数组中判断岛屿是连接在一块的？
    //     扫面四周，看是否有为‘1’的元素
    //如何确定两个岛屿可以合并？
    //     扫描四周，有为‘1’的元素就合并
    //如何合并？
    //     直接Union函数来合并
    //对于这种二维数组，如何初始化帮派？
    //     将二维数组所有元素看成一个点，所有元素自成一派

    private int[][] dir = { { 0, 1 }, { 1, 0 } };//用来比较下方和右方
    private int[] F = null;
    private int count = 0;
    public int numIslands(char[][] A) {
        if (A == null || A[0] == null) {//A[0] 表示二维数组中的第O行，本质也是数组
            return 0;
        }

        final int R = A.length;
        final int C = A[0].length;

        Init(R * C);

        // 统计黑色像素的个数
        int blackNumber = 0;

        // 每个白色像素点与周围的点进行Union
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (A[r][c] == '1') {
                    // 与四周的点进行Union
                    for (int d = 0; d < 2; d++) {
                        final int nr = r + dir[d][0];
                        final int nc = c + dir[d][1];
                        if (!(nr < 0 || nr >= R || nc < 0 || nc >= C)) {//不越界
                            if (A[nr][nc] == '1') {
                                Union(r * C + c, nr * C + nc);
                            }
                        }
                    }
                } else {
                    blackNumber++;
                }
            }
        }

        return count - blackNumber;
    }


    private void Init(int n) {
        F = new int[n];
        for (int i = 0; i < n; i++) {
            F[i] = i;
        }
        count = n;
    }

    private int Find(int x) {
        if (x == F[x]) {
            return x;
        }
        F[x] = Find(F[x]);
        return F[x];
    }

    private void Union(int x, int y) {
        if (Find(x) != Find(y)) {
            count--;
        }
        F[Find(x)] = Find(y);
    }


    /**方法二：感染函数
      遍历整个二维数组，如果当前为1，则进入感染函数
      感染函数：将与当前元素的所有相邻的且为1的元素进行感染，变成为2 这里可以为一个递归过程
     */
    private int islands;
    public int numIslands3(char[][] grid) {
        islands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1'){//进入感染函数
                    infect(grid,i,j);
                    islands++;
                }
            }
        }
        return islands;
    }

    private void infect(char[][] grid, int i, int j) {
        //边界条件
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1'){
            return;
        }
        grid[i][j] = '2';
        //递归
        infect(grid,i - 1, j);
        infect(grid,i + 1, j);
        infect(grid,i, j - 1);
        infect(grid,i, j + 1);
    }



















    public int numIslands4(char[][] grid) {
         if (grid == null || grid.length == 0){
             return 0;
         }
         int ans = 0;
         final  int m = grid.length;
         final  int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1'){
                    infect2(grid,i,j);
                    ans++;
                }
            }
        }
        return ans;
    }

    private void infect2(char[][] grid, int i, int j) {
        final  int m = grid.length;
        final  int n = grid[0].length;
        if (i >= m || j >= n || i < 0 || j < 0){//边界条件
            return;
        }
        if (grid[i][j] != '1'){//只感染‘1’
           return;
        }
        grid[i][j] = '2';
        //感染上下左右的元素
        infect2(grid, i - 1, j);
        infect2(grid, i + 1, j);
        infect2(grid, i, j+1);
        infect2(grid,i,j - 1);
    }
}
